package com.fyl.leetcode.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author:fyl
 * @date 2021/5/8 15:40
 * @Modified By:
 * @Modified Date:
 * @Description:
 *题目描述：气球在一个水平数轴上摆放，可以重叠，飞镖垂直投向坐标轴，使得路径上的气球都被刺破。求解最小的投飞镖次数使所有气球都被刺破。
 *
 * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
 * 输出：2
 * 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
 *
 * 也是计算不重叠的区间个数，不过和 Non-overlapping Intervals 的区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。
 */
public class MinNumArrowsBurstBalloons {
    public static int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int count = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= end) {
                continue;
            }
            end = points[i][1];
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] points = {{1,2},{2,3},{3,4},{4,5}};
        System.out.println(findMinArrowShots(points));
    }
}
